package prefixTree;

import prefixTree.TrieNode;

/**
 * 题目 ：前缀树（Trie）的实现
 * 题目详述：
 * Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。
 * 这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
 *
 * 请你实现 Trie 类：
 * Trie() 初始化前缀树对象。
 * void insert(String word) 向前缀树中插入字符串 word 。
 * boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
 * boolean startsWith(String prefix) 如果之前已经插入的字符串word 的前缀之一为 prefix ，返回 true ；否则，返回 false
 */
public class Trie {
    private TrieNode root;
    public Trie() {
        // 初始化根节点，使得根节点数据结构为自定义的前缀树中节点类型
        root = new TrieNode();
    }

    public void insert(String word) {
        /**
         *  前缀树插入 ：即，从前缀树的根节点开始，同时遍历整个字符串，相互进行比较，看两者之间的字符是否一致；
         *  （1）将所传入的字符串转化为字符数组；
         *  （2）判断当前正在遍历节点的子节点数组，是否包含字符串中当前正在遍历字符所对应的前缀树节点；
         */
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            // 即，前缀树中当前正在遍历节点的子数组中，还未保存了字符串中当前正在遍历的字符的话，
            // 需要去创建新的前缀树节点，同时将其加入到当前正在遍历节点的子数组中，同时及那个正在遍历的节点下移到新加入的前缀树节点；
            if(node.children[c - 'a'] == null){
                // 即，向当前正在遍历的node前缀树节点中，当前正在遍历字符所应该存在的位置，插入新的前缀树节点；
                // 即，代表了当前正在遍历节点的子节点数组，已经包含字符串中当前正在遍历字符所对应的前缀树节点
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
            // 即，前缀树中当前正在遍历节点的子数组中，已经保存了字符串中当前正在遍历的字符的话，直接将当前遍历节点下移，即可；
        }
        // 对于新插入的单词遍历完成后，需要将最后一个字符所对应的前缀树节点的isWord改为true；即代表根节点到此节点路径所代表的字符串为一个完整的单词
        node.isWord = true;
    }

    public boolean search(String word) {
        /**
         * 思路 ：由于search函数，所代表的是，去查询之前新增入前缀树中的单词;
         * (1)即，遍历完整个单词，若是单词中的所有字符都在前缀树中 && 最后一个字符所对应的前缀树节点的isWord为true；即说明当前单词在前缀树中存在；；
         * (2)即，判断当前要去查询的单词的所有字符是否存在于前缀树中；
         */
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if(node.children[c - 'a'] == null){
                // 若是未找到字符的话，直接返回false即可；
                return false;
            }
            // 若是找到字符的话，即后移到所找到字符对应的前缀树节点；
            node = node.children[c - 'a'];
        }
        // 即，若是当前单词的所有字符都在前缀树中存在；那么就需要判断其是否为之前向前缀树中插入的单词
        return node.isWord;
    }

    public boolean startsWith(String prefix) {
        /**
         * 思路 ：startsWith函数，即去判断前缀树中是否存在以当前字符串为前缀（prefix）的单词；
         */
        TrieNode node = root;
        // 只需要去遍历前缀（prefix），去判断当前前缀（prefix）中的所有字符是否存在于前缀树中
        for (char c : prefix.toCharArray()) {
            if(node.children[c - 'a'] == null){
                // 若是未找到字符的话，直接返回false即可；
                return false;
            }
            // 若是找到字符的话，即后移到所找到字符对应的前缀树节点；
            node = node.children[c - 'a'];
        }
        // 即，若是所要查询前缀（prefix）的所有字符都在前缀树中存在，即返回值为true；
        return true;
    }
    /**
     * 分析 ：
     * （1）时间复杂度 ：若是单词长度为n个字符的话，所以无论新增，查找还是查询前缀，所需要的时间复杂度：O（n）；
     */
}
